css: Add fast-path for parent selector matching
authorBenjamin Otte <otte@redhat.com>
Sun, 26 Jan 2020 03:37:17 +0000 (04:37 +0100)
committerBenjamin Otte <otte@redhat.com>
Tue, 28 Jan 2020 01:17:03 +0000 (02:17 +0100)
commit170130f1d9c15e4274a24b9327fe01d36ad84290
tree0a07692fba8a8b378ed08095480b7e5885fc3dd1
parent6aac56e144e1088565db7d29591fc0bd9e3e509d
css: Add fast-path for parent selector matching

Add a fast path for parent selector matching that uses a bloom filter to
quickly discard selectors that can't possibly match.

Keep in mind that we match using a bloom filter, so we might
accidentally include too many selectors when hash/bucket collisions
occur.
That's not a correctness problem though, because we'll do a real check
afterwards.

The idea for this change is taken from browsers, in particular WebKit.
14 files changed:
gtk/gtkcountingbloomfilterprivate.h [new file with mode: 0644]
gtk/gtkcssnode.c
gtk/gtkcssnodedeclaration.c
gtk/gtkcssnodedeclarationprivate.h
gtk/gtkcssnodeprivate.h
gtk/gtkcssprovider.c
gtk/gtkcssselector.c
gtk/gtkcssselectorprivate.h
gtk/gtkcssstaticstyle.c
gtk/gtkcssstaticstyleprivate.h
gtk/gtkcsstransientnode.c
gtk/gtkstylecascade.c
gtk/gtkstyleprovider.c
gtk/gtkstyleproviderprivate.h